CSP201903

2024-07-13 06:18| 来源: 网络整理| 查看: 265

点击此处直达题目分析在这里插入图片描述

题目分析：这道题光是理解题意就花了好长时间，感觉出题人在写小说，但是把题目所描述的问题理清了之后，这道题编写起来并不难。

我在看题目的时候，有一个地方绕了好长时间。题目中给举了一个n=3的例子，也就是下面这张图。在这里插入图片描述这个看起来还是比较好理解的，就是图中横着的每一行算是一个组（组的概念是我自己加的，题目中并未提及此概念），每一个组中有一个校验盘（实际上一个条带），在图中是灰色的方框P，组内的其它条带都是用来存储数据的。校验条带的选取规则和数据条带的选取规则也比较好理解，虽然前面有一句话我没看懂，在这里插入图片描述怎么还用条带来存储条带？但先不管它，继续往后看到了样例2，

我被它方框里的编号给弄糊涂了，前面的图的编号是横着进行编的，怎么到了这儿变成了先竖着编再横着编了。其实这个图中的编号是内存块在整个RAID5中的编号，而前面的图的编号是RAID5中每个条带的编号，只是为了说明条带的编号规则。在下面的图中，我又把条带的编号给补上了，每两个内存块是一个条带。在这里插入图片描述

数据结构定义一个string类型的数组，用来存储每个磁盘的内容，因为子任务说明中n不超过1000，因此数组定义如下

string Disk[1000];

在使用这个数组时，可以把它看成如下的形式在这里插入图片描述 Disk[0]存储第0个硬盘的内容，Disk[1]存储第1个硬盘的内容…因为磁盘中每一块的大小是四个字节，每两个字符占一个字节，因此Disk[0]的前八个字符可以表示第0个磁盘的第0块，第8~15个字符表示第0个磁盘的第1块，依次类推。

下面的代码是此程序的核心

int stripeRow; //要查询的块所在的条带的行号 int pCol; //校验块P所在的列号 int stripeOrder; //要查询的块在第几个条带上 int rowMin; //当前行的最小条带编号 int col; //要查询的块所在的磁盘 int blockOrder; //要查询的块在磁盘的编号 stripeOrder = b / s; stripeRow = stripeOrder / (n - 1); pCol = n - 1 - stripeRow % n; rowMin = stripeRow * (n - 1); col = (pCol+(stripeOrder - rowMin) + 1) % n; blockOrder = stripeRow * s + b % s;

它的功能就是定位到要查询的块在哪个磁盘上，是某个磁盘的第几块。我们以题目中的实例2为例来说明这段代码的执行过程，假设要找b=7位置。在这里插入图片描述 b=7，s=2，所以stripeOrder=3，说明要查询的块在第三个条带，第三个条带在RAID5中所在的行号为stripeRow=1，第一行的校验块P所在的列是pCol=1，第一行编号最小的条带的编号是rowMin=2,所要找的块b=7所在的列col=0，此块是第0个磁盘的第blockOrder=3块。注意事项最初写完代码进行测试的时候，总是显示超时，于是又回去想办法降低时间复杂度，一通操作之后始终运行超时。最终从网上找到了解决办法，在代码里加一句ios::sync_with_stdio(false);就可以了。至于原理，是因为C++为了兼容C，所以导致cin和cout变得异常缓慢，上述语句就是禁止兼容C语言，所以输入输出就变块了。源代码

#include using namespace std; string Disk[1000]; int n, s, l; void Inquire(int blockNum, int col, long long & result) { string block; //存放每个磁盘中某个块的内容 long long numer; //将字符串按照十六进制转换成数值 bool flag = true; for (int i = 0; i //用try catch语句，防止Disk[i]为空时引发未经处理的异常 block = Disk[i].substr(8 * blockNum, 8); numer = stoll(block,nullptr,16); if (flag) { result = numer; flag = false; } else { result = result ^ numer; } } catch(...){} } } int main() { ios::sync_with_stdio(false); int m; int b; //待查询的块编号 int index; int length = 0; //记录每个磁盘存了多个了字符 cin >> n >> s >> l; int count = n - l; //用来记录缺失的磁盘数 for (int i = 0; i cin >> b; if (b >= (length / 8) * (n - 1)) //指定的块超出阵列的总长度 { cout //待查询的磁盘不存在且缺失了两块以上的磁盘 cout

【本文地址】

公司简介

联系我们